07 时序差分方法

TD Learning of State Values

算法公式：

v_{t+1}(s_t) = v_{t}(s_t) - \alpha_t(s_t)[v_t(s_t) - [r_{t+1} + \gamma v_t(s_{t+1})]]

其中（最后一个方括号）

\bar{v_t} = r_{t+1} + \gamma v_t(s_{t+1})

称为TD target，

\delta_t = v_t(s_t) - \bar{v_t}

称为TD error。

对原公式变形，可以得到

\begin{gather*} |v_{t+1}(s_t) - \bar{v_t}| = |1 - \alpha_t(s_t)||v_t(s_t) - \bar{v_t}| \\ |v_{t+1}(s_t) - \bar{v_t}| \le |v_t(s_t) - \bar{v_t}| \end{gather*}

随着迭代， $v$ 将会越来越靠近 $\bar{v_t}$ ，所以 $\bar{v_t}$ 代表target。

而 $\delta_t$ 实际上是两个时刻量的相减

\delta_t = v_t(s_t) - [r_{t+1} + \gamma v_t(s_{t+1})]

可以证明如果 $v_t = v_\pi$ ，则 $\delta_t$ 为0，所以 $\delta_t$ 代表了现有状态值和真实值之间的误差。

这里的TD算法只能用于估计状态价值，但是不能估计行动价值/最优策略。事实上，这种公式也是对贝尔曼公式（期望形式）的求解。

v_\pi(s) = E[R + \gamma v_\pi(S\prime)|S=s]

可以看出，TD learning在episode的每一步都可以更新，即它是在线算法。而蒙特卡洛等必须在某个episode结束后才能更新，为离线算法。此外，TD是自举的，方差（variance）较小（只涉及了较少的随机变量）；蒙特卡洛不是自举的，由于涉及到整个episode的随机变量，方差较大。但由于TD依赖初始推测，TD是有偏的（bias）；蒙特卡洛是无偏的。

Sarsa

q_{t+1}(s_t,a_t)=q_t(s_t, a_t) - \alpha_t(s_t, a_t)[q_t(s_t, a_t) - [r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})]]

其中 $q_t$ 是 $q_\pi$ 的估计值。

Sarsa也是对贝尔曼公式的求解，但是写为action value的形式。

将Sarsa和PI结合，就可以求出最优策略。

对每个episode
- 如果 $s_t$ $s_{t}$ 不是目标状态
  - 每次到达新状态
  - 更新 $q$
  - 通过 $max~q$ 更新soft policy

Expected Sarsa

q_{t+1}(s_t, a_t)=q_t(s_t, a_t) - \alpha_t[q_t(s_t, a_t) - [r_{t+1} + \gamma E[q_t(s_{t+1},A)]]]

这种方式将目标值（部分）从 $q_t(s_{t+1}, a_{t+1})$ 改为了 $E[q_t(s_{t+1},A)]$ ，不需要对 $a_{t+1}$ 进行采样，随机变量变少，随机性减少；但期望增加了计算量。

N-Step Sarsa

N-Step Sarsa是介于Sarsa和蒙特卡洛之间的算法。

算法	公式
蒙特卡洛	$G_t = R_{t+1} + \gamma R_{t+2} + ...$
Sarsa	$G_t = R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1})$
n-step Sarsa	$G_t = R_{t+1} + \gamma R_{t+2} + ... \gamma^n q_\pi(S_{t+n}, A_{t+n})$

N-Step不是纯粹的在线/离线算法；对于 $G_t$ ，它需要等到 $R_{t+n}$ 到 $R_{t+1}$ 都计算完成才能更新。

q_{t+n}(s_t, a_t) = q_{t+n-1}(s_t, a_t) - \alpha_{t+n-1}(s_t, a_t)[q_{t+n-1}(s_t, a_t) - [r_{t+1} + \gamma r_{t+2} + ... + \gamma^n q_{t+n-1}(s_{t+n}, a_{t+n})]]

（暂时没有很理解这里的 $q_{t+n}$ 下标的含义，感觉像一个代号？）

Q-Learning

Q-Learning可以直接估计最优的action value，因此舍去了PI这一步。

q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)[q_t(s_t, a_t) - [r_{t+1} + \gamma~max~q_t(s_{t+1}, a)]]

这个公式实质上是求解BOE的另一种形式。

q(s,a) = E[R_{t+1} + \gamma~max~q(S_{t+1}, a)|S_{t}=s, A_t = a]

Q-Learning是off-policy的，所以它实际可以写出两种形势。on-policy的形式和Sarsa相同，只是PE改为了Q-Learning的公式。

off-policy中，除了最优策略 $\pi_T$ ，还有一个行为策略 $\pi_b$ 。 $\pi_b$ 用于广泛探索（例如，遍历每个 $s$ ，给每个 $a$ 均等概率）；对每个 $\pi_b$ 得到的轨迹，进行如下步骤

对每个轨迹的 $t=0,1,...$ $t = 0, 1, ...$
- PE
  - $q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t)[q_t(s_t, a_t) - [r_{t+1} + \gamma~max~q_t(s_{t+1}, a)]]$
- PI
  - $\pi_{T, t+1}(a|s_t) = 1~if~a = arg~max_aq_{t+1}(s_t, a)$
  - $\pi_{T, t+1}(a|s_t) = 0~otherwise$

On-Policy和Off-Policy

策略分为behavior policy和target policy。

behavior policy（行为策略）：用于产生经验性的样本（通过和外部环境交互得到经验）
target policy（目标策略）：持续优化以得到最优策略

当某种策略的behavior policy和target policy永远一致，则这种策略为on-policy；如果允许不一致，则为off-policy。

behavior policy的探索性较强，off-policy可以更好得利用探索得到的经验；而如果behavior policy和target policy相同，可能无法充分地进行探索。

算法	特征
蒙特卡洛	on-policy
Sarsa	on-policy
Q-Learning	off-policy